Given the head of a linked list, remove the nth node from the end of the list and return its head.

給一個 linked list 並移除倒數第 n 個 node。

Example

Input: 1 -> 2 -> 3 -> 4 -> 5, n = 2;
Output: 1 -> 2 -> 3 -> 5

Step

1. 利用快慢雙指針，建立一個 node 連在 head 前面並讓慢指針指向 node
   
   

2. 設定慢指針與快指針
   

3. 讓快指針先跑 n 個 node，再讓兩個指針一起跑，跑到快指針抵達 head 的最後一個 node，這樣就會使慢指針剛好停在要被移除的 node 的前一個 node。
   

4. 將慢指針指到的 node 連接到下下個 node
   

Coding

/**
 * @param {ListNode} head
 * @param {number} n
 * @return {ListNode}
 */
var removeNthFromEnd = function(head, n) {
    if(head == null) return head; 

    var node = new ListNode(0);
    node.next = head;

    let slow = node;
    let fast = head;
    while (n > 0) {
        fast = fast.next;
        n--;
    }

    while(fast){
        fast = fast.next;
        slow = slow.next;
    }

    if(slow.next === null){
        slow.next = null ;
    } else {
        slow.next = slow.next.next;
    }

    return node.next;
};

Time complexity: O(n)